PART 1. Optimization without constraints. Single variable.

Example 1.1 Optimize $f(x)=-x^2+2x+4$

Look for stationary points

$f'(x)=-2x+2=0\Rightarrow x=1$

The condition that the derivative equals zero at the point is necessary for the point to be an extremum. Point with zero derivative may be an extremum, but doesn't have to be. Point without zero derivative can't be an extremum. We may call this the (simplified) First Order Necessary Condition (FONC).

In [1]:
if(!require(Deriv)) install.packages('Deriv')
library("Deriv")
f<-function(x){-x^2+2*x+4}
f_<-Deriv(f)
x<-seq(from=-5,to=5,by=0.1)
plot(x,f(x),type="l",col="blue",xlim<-c(-2,4),ylim<-c(-8,8),xlab='',ylab='')
lines(x,f_(x),type="l",col="red") 
legend(-2,8, legend=c("f(x)=-x^2+2*x+4", "f'(x)=-2x+2"),col=c("blue", "red"), lty=1, cex=1.3)
grid()
Loading required package: Deriv

Warning message:
"package 'Deriv' was built under R version 3.6.3"

Check the second derivative value at the stationary points

if $f''(x)>0 \Rightarrow $ x is a local minimum point
if $f''(x)<0 \Rightarrow $ x is a local maximum point
if $f''(x)=0 \Rightarrow $ The test is inconclusive. One has to investigate further, by taking more derivatives,or getting more information about the graph.

Satisfying both conditions, that is zero first derivative and nonzero second derivative is sufficient to claim that the point is a local extremum of the function. Nonzero second derivative along with satisfied FONC may be then called the (simplified) Second Order Sufficient Condition (SOSC).
in our case: $f''(x=1)=-2$, and the point is a local maximum.

Example 1.2 Optimize $f(x)=x^3$

Look for stationary points

$f'(x)=3x^2=0\Rightarrow x=0$

Check the second derivative value at the stationary points

$f''(x=0)=6x=0$, and the test is inconclusive

The fact that the test is inconclusive, means that the point may be an extremum, but doesn't have to be. This means that satisfying the zero first derivative condition and zero second derivative condition doesn't necessarily mean that the point isn't an extremum. Zero first derivative and $f''(x)\leq0 \lor f''(x)\geq0$ may be then called the (simplified) Second Order Necessary Condition (SONC).

Moving back to the example, one may compute the concavity on the right and on the left of 0, and deduct that 0 is an inflection point. This is not the focus of our lecture.

In [2]:
f<-function(x){x^3}
f_<-Deriv(f)
x<-seq(from=-2,to=2,by=0.1)
plot(x,f(x),type="l",col="blue",xlab='',ylab='')
lines(x,f_(x),type="l",col="red")
legend(-2,8, legend=c("f(x)=x^3"),col="blue", lty=1, cex=1.5)
grid()

PART 2. Optimization without constraints. Multiple variables.

Example 2.1 Optimize $f(x,y)=-x^2-2y^2$

1. Satisfy First Order Necessary Condition (FONC)

Let $f$ be defined on a set S in $R^n$ and let $x^*=(x_1^*,\dots ,x_n^*)$ be an interior point in S at which f has partial derivatives. A necessary condition for $x^*$ to be a maximum or minimum point for f is that $x^*$ is a stationary point for $f$ - that is, it satisfies the equations

$f_i'(\boldsymbol x)=0,\quad\quad i=1,\dots,n$

Analogically to the case with one variable, we need to search for points in which the gradient is the zero vector. (This means that all of the partial derivatives need to equal zero):
$f_x'=-2x=0\Rightarrow x=0$
$f_y'=-4y=0\Rightarrow y=0$

The candidate solution is the point (0,0)

2. Check the Second Order Conditions

In the case of multiple variables, all combinations of second partial derivatives need to be checked. They are gathered in a matrix called the Hessian matrix.

Examine the Hessian matrix of the equation (the matrix of second derivatives)

$H=\begin{bmatrix}f''_{xx}\;\;f''_{xy} \\f''_{yx}\;\;\;\;f''_{yy}\end{bmatrix}= \begin{bmatrix}-2\;\;\;\;\;\;0 \\0\;\;\;\;-4\end{bmatrix}$

Matrix definiteness

A symmetric matrix $A \in {\rm I\!R}^{n\times n}$ is called positive definite if $x^TAx>0$ for every $\boldsymbol 0\neq \boldsymbol x\in {\rm I\!R}^n$
A symmetric matrix $A \in {\rm I\!R}^{n\times n}$ is called negative definite if $x^TAx<0$ for every $\boldsymbol 0\neq \boldsymbol x\in {\rm I\!R}^n$
A symmetric matrix $A \in {\rm I\!R}^{n\times n}$ is called positive semidefinite if $x^TAx\geq0$ for every $\boldsymbol 0\neq \boldsymbol x\in {\rm I\!R}^n$
A symmetric matrix $A \in {\rm I\!R}^{n\times n}$ is called negative semidefinite if $x^TAx\leq0$ for every $\boldsymbol 0\neq \boldsymbol x\in {\rm I\!R}^n$
A symmetric matrix $A \in {\rm I\!R}^{n\times n}$ is called indefinite if there exists $\boldsymbol x$ and $\boldsymbol y \in {\rm I\!R}^n$ such that $x^TAx>0$ and $y^TAy<0$

The Second-Order Sufficient Condition (SOSC) for a minimum in an extremum is that the Hessian matrix is positive definite. Second Order Necessary Condition (SONC) for a minimum in an extremum is that the Hessian matrix is positive semidefinite.

The Second-Order Sufficient Condition for a maximum in an extremum is that the Hessian matrix is negative definite. Second Order Necessary Condition for a maximum in an extremum is that the Hessian matrix is negative semidefinite.

Check concavity of the Hessian matrix

$\quad [z_1\;z_2]\begin{bmatrix}-2\;\;\;\;0 \\0\;-4\end{bmatrix}\begin{bmatrix}z_{1} \\z_{2}\end{bmatrix}=-2z_1^2-4z_2^2$

The Hessian is negative definite, and thus the point is the maximum.

Below is the code for the solution in R. The code needed to be adjusted (precisely the function had to be multiplied by -1) for the fact that solnp function minimizes, not maximizes the function.

In [3]:
library(Rsolnp)
fn <- function(x) {x[1]^2 + 2*x[2]^2}
x0 <- c(1, 1) # setup any init values
sol1 <- solnp(x0, fun = fn)
sol1[1]
sol1[2]
sol1[4]
sol1[5]
Iter: 1 fn: 8.923e-15	 Pars:  -0.00000006580 -0.00000004793
Iter: 2 fn: 8.923e-15	 Pars:  -0.00000006580 -0.00000004792
solnp--> Completed in 2 iterations
$pars =
  1. -6.57979498777722e-08
  2. -4.79231629986138e-08
$convergence = 0
$lagrange = 0
$hessian =
A matrix: 2 × 2 of type dbl
1.9927444650.001905294
0.0019052943.999499672

pars Optimal Parameters.
convergence Indicates whether the solver has converged (0) or not (1 or 2).
lagrange #The vector of Lagrange multipliers.
hessian The Hessian of the augmented problem at the optimal solution.

In [4]:
if(!require(plotly)) install.packages('plotly')
library("plotly")
x = seq(from=-1,to=1,by=0.1)
y = seq(from=-1,to=1,by=0.1)
z=outer(x,y,function(x,y)-x^2-2*y^2)
fig <- plot_ly(type = 'surface',x = x,y = y,z = z)
fig
Loading required package: plotly

Loading required package: ggplot2


Attaching package: 'plotly'


The following object is masked from 'package:ggplot2':

    last_plot


The following object is masked from 'package:stats':

    filter


The following object is masked from 'package:graphics':

    layout


Example 2.2 Optimize $f(x,y)=x^2-y^2$

1. Satisfy First Order Necessary Condition (FONC)

We search for points in which the gradient is the zero vector.
$f_x'=2x=0\Rightarrow x=0$
$f_y'=-2y=0\Rightarrow y=0$
The candidate solution is the point (0,0)

2. Check the Second Order Conditions

Examine the Hessian matrix of the equation

$H=\begin{bmatrix}f''_{xx}\;\;f''_{xy} \\f''_{yx}\;\;\;\;f''_{yy}\end{bmatrix}= \begin{bmatrix}2\;\;\;\;\;\;0 \\0\;\;\;\;-2\end{bmatrix}$

Check concavity of the Hessian matrix

$\quad [z_1\;z_2]\begin{bmatrix}2\;\;\;\;0 \\0\;-2\end{bmatrix}\begin{bmatrix}z_{1} \\z_{2}\end{bmatrix}=2z_1^2-2z_2^2$

The Hessian matrix is indefinite. Its concavity changes depending on the $z_1$ and $z_2$ values. The point is the saddle point.

In [5]:
library(Rsolnp)
fn <- function(x) {x[1]^2 - x[2]^2}
x0 <- c(1, 1) # setup any initial values
sol1 <- solnp(x0, fun = fn)
sol1[1]
sol1[2]
sol1[4]
sol1[5]
Iter: 1 fn: -36175652352.0000	 Pars:  -2048969401.79165  2048969410.61942
Iter: 2 fn: -1.107e+16	 Pars:  -273203202322.96036  273203222587.33817
solnp--> Solution not reliable....Problem Inverting Hessian.
$pars =
  1. -273203202322.96
  2. 273203222587.338
$convergence = 2
$lagrange = 0
$hessian =
A matrix: 2 × 2 of type dbl
219248922219248904
219248904219248886
In [6]:
x = seq(from=-1,to=1,by=0.1)
y = seq(from=-1,to=1,by=0.1)
z=outer(x,y,function(x,y)x^2-y^2)
fig <- plot_ly(type = 'surface',x = x,y = y,z = z)
fig

PART 3. Optimization with equality constraints.

A general optimization problem with equality constraints is of the form

max(min) $f(x_1,\dots,x_n)$ subject to $\begin{equation} \begin{cases} g_1(x_1,\dots,x_n)=b_1\\ \dots \\ g_m(x_1,\dots,x_n)=b_m\\\end{cases}\end{equation}$ $(m<n)$

In vector formulation, the problem is
max(min) $f(\boldsymbol x)$ subject to $g_j(\boldsymbol x)=b_j, j=1,\dots,m (m<n)$

Example 3.1 Optimize $f(x,y)=x^2+y^2$ subject to $g(x,y)=x^2+2y^2-1=0$

The standard procedure for solving this problem is to:

1. Define the Lagrangian


$\mathcal{L}(\boldsymbol x)=f(\boldsymbol x)-\lambda_1g_1(\boldsymbol x)-\dots-\lambda_mg_m(\boldsymbol x)$, where the $\lambda's$ are called the Lagrange multipliers.

In our example the Lagrangian equals $\mathcal{L}(x,y)=x^2+y^2-\lambda_1(x^2+2y^2-1)$

2. Satisfy the First Order Necessary Condition

$\frac{\partial\mathcal{L}(\boldsymbol x)}{\partial(x_i)} = \frac{\partial f(\boldsymbol x)}{\partial x_i}-\sum_{j=1}^{m}\lambda_j\frac{\partial g_j(\boldsymbol x)}{\partial x_i}=0,\;\;\;\;\; i=1,\dots,n$

This is equal to saying that we want to find the points at which the gradient of the Lagrangian equals the zero vector. Studying the equation we may conclude that the condition is satisfied at the points where the gradient of the function is a linear combination of gradients of constraints.

We also require that the gradients of the constraints are linearly independent at the analyzed points. This requirement is called constraint qualification.

Our First Order Necessary Conditions are:
A) $\frac{\partial\mathcal{L}}{\partial x}=2x-2\lambda_1x=0$
B) $\frac{\partial\mathcal{L}}{\partial y}=2y-4\lambda_1y=0$
C) $\frac{\partial\mathcal{L}}{\partial \lambda_1}=-x^2-2y^2+1=0 \Rightarrow x^2+2y^2-1=0$

As we can see, satisfying the FONC means finding the points at which partial derivatives are equal to zero and constraint is satisfied. Pointing out the C) condition seems redundant, as we could just use the constraint itself.


Solving the set of equations, we have:
A) $2x(1-\lambda_1)=0 \Rightarrow x=0 \lor \lambda_1=1$
B) $2y(1-2\lambda_1)=0 \Rightarrow y=0 \lor \lambda_1=\frac{1}{2}$

Above two equations create four cases that need to be analyzed:

1) $x=0 \land y=0 \Rightarrow $ constraint not satisfied
2) $x=0\land\lambda_1=\frac{1}{2}\Rightarrow2y^2=1\Rightarrow y=\frac{1}{\sqrt{2}}\lor y=-\frac{1}{\sqrt{2}}$
3) $y=0 \land \lambda_1=1 \Rightarrow x^2=1 \Rightarrow x=1 \lor x=-1 $
4) $ \lambda_1=\frac{1}{2} \land \lambda_1=1 \Rightarrow$ contradiction

Cases 2) and 3) result in four points that meet the FONC criteria, lets call them $P_1$,$P_2$,$P_3$ and $P_4$ respectively.

<
Point xy $\lambda_1$ f(x,y)
$P_1$ 0 $\frac{\sqrt{2}}{2}$$\frac{1}{2}$$\frac{1}{2}$
$P_2$ 0$\frac{-\sqrt{2}}{2}$$\frac{1}{2}$$\frac{1}{2}$
$P_3$ 1 $0$$1$$1$
$P_4$ -1 $0$$1$$1$

3. Check the Second Order Condition - The Hessian matrix definiteness

We introduce the idea of the Jacobian. Jacobian is a matrix of first derivatives, in the case of our example it is basically a gradient of our one active constraint.

$$ \mathbf{J} = \frac{d \mathbf{f}}{d \mathbf{x}} = \left[ \frac{\partial \mathbf{f}}{\partial x_1} \cdots \frac{\partial \mathbf{f}}{\partial x_n} \right] = \left[ \frac{\partial \mathbf{g}}{\partial x} \frac{\partial \mathbf{g}}{\partial y} \right] = \left[ 2x \; 4y \right] $$

Once again we need to check the definiteness of the Hessian matrix (precisely the definiteness of the Hessian of the Lagrangian) in the nullspace of the Jacobian. The vectors "surrounding" the Hessian need to be the nullspaces of the corresponding Jacobian. How to calculate the nullspace?

$J(\boldsymbol x^*)*Z=0$

$\cdot$ Case $P_1$: $[0\;\;2\sqrt{2}]\begin{bmatrix}z_{1} \\z_{2}\end{bmatrix}=0\Rightarrow 2\sqrt{2}z_2=0\Rightarrow z_2=0\Rightarrow Z=\begin{bmatrix}z_{1} \\ 0\end{bmatrix}$

$\cdot$ Case $P_2$: $[0\;\;-2\sqrt{2}]\begin{bmatrix}z_{1} \\z_{2}\end{bmatrix}=0\Rightarrow -2\sqrt{2}z_2=0\Rightarrow z_2=0\Rightarrow Z=\begin{bmatrix}z_{1} \\ 0\end{bmatrix}$

$\cdot$ Case $P_3$: $[2\;\;\;0]\begin{bmatrix}z_{1} \\z_{2}\end{bmatrix}=0\Rightarrow 2z_1=0\Rightarrow z_1=0\Rightarrow Z=\begin{bmatrix}0 \\ z_2\end{bmatrix}$

$\cdot$ Case $P_4$: $[-2\;\;\;0]\begin{bmatrix}z_{1} \\z_{2}\end{bmatrix}=0\Rightarrow -2z_1=0\Rightarrow z_1=0\Rightarrow Z=\begin{bmatrix}0 \\ z_2\end{bmatrix}$

We calculated the nullspace vectors of each candidate point. Now, how does the process of calculating the definiteness of Hessian matrix look in the case of optimization with equality constraints? It is very similar to previous cases, but now the Hessian is based on our Lagrangian function.

$H=\begin{bmatrix}f''_{xx}\;\;f''_{xy} \\f''_{yx}\;\;\;\;f''_{yy}\end{bmatrix}\;\;\;$ of $\;\;\;\mathcal{L}(x,y)=x^2+y^2-\lambda_1(x^2+2y^2-1)$

$H_L=\begin{bmatrix}2-2\lambda_1\;\;\;\;\;0 \\0\;\;\;\;2-4\lambda_1\end{bmatrix}$ The $H_L$ may differ between points, as $\lambda_1$ differ.

Now for each point calculate $Z^T*H_L*Z$. We can see that the nullspace $Z$ of the two points $P_1$ and $P_2$ is indifferent, similarly as their $\lambda_1$ values. This means that the definiteness of their Hessian matrices will be equal. Judging by the same conditions, the definiteness of Hessian matrices of points $P_3$ and $P_4$ is also the same. Therefore:

$\cdot$ Case $P_1$ and $P_2$: $\quad [z_1\;\;0]\begin{bmatrix}1\;\;\;\;0 \\0\;\;\;\;0\end{bmatrix}\begin{bmatrix}z_{1} \\0\end{bmatrix}=z_1^2 \Rightarrow$ The Hessian is positive definite, the $P_1$ and $P_2$ points are the minima.
$\cdot$ Case $P_2$ and $P_3$: $\quad [0\;\;z_2]\begin{bmatrix}0\;\;\;\;0 \\0\;-2\end{bmatrix}\begin{bmatrix}0 \\z_{2}\end{bmatrix}=-2z_2^2 \Rightarrow$ The Hessian is negative definite, the $P_3$ and $P_4$ points are the maxima.

PART 4. Optimization with inequality constraints

Example 4.1 Maximize $f(x,y)=x^2+2y$ subject to $\begin{equation} \begin{cases} g_1=x^2+y^2\leq5\\g_2=y\geq0\\\end{cases}\end{equation}$

1. Standardize the form

Maximize $f(x,y)=x^2+2y$ subject to $ \begin{equation} \begin{cases} g_1=x^2+y^2-5\leq0\\ g_2=-y\leq0\\ \end{cases} \end{equation}$

2.Define the Lagrangian

$L=x^2+2y-\lambda_1(x^2+y^2-5)-\lambda_2(-y)$

3.Define the First Order Necessary Conditions

A)$\frac{\delta_L}{\delta_x}=2x-2\lambda_1x=0\Rightarrow2x(1-\lambda_1)=0\Rightarrow x=0 \lor \lambda_1=1$

B)$\frac{\delta L}{\delta y}=2-2\lambda_1y+\lambda_2=0$

C)$\lambda_1\geq0\;(\lambda_1=0\;\;if\;\;x^2+y^2-5<0)$

D)$\lambda_2\geq0\;(\lambda_2=0\;\;if\;\;y>0)$

Above conditions are the Karush-Kuhn-Tucker, or KKT conditions. The additional C) and D) conditions are called complementary slackness conditions.

4.Examine four cases

Case 1. We are searching for feasible points at the crossover of constraints

$\cdot$ C) and D) are binding $\Rightarrow x^2+y^2=5,y=0$

$\quad$ case A)$\;x=0 \Rightarrow x^2+y^2\neq5$ contradiction

$\quad$ case A)$\;\lambda_1=1\Rightarrow \lambda_2=-2$ contradiction

Case 2. We are searching for feasible points at the C) constraint, inside the D) constraint

$\cdot$ C) is active, D) is inactive $\Rightarrow x^2+y^2=5,\lambda_2=0,y>0$

$\quad$ case A)$\;x=0\Rightarrow y=\pm\sqrt5$

$\quad \quad$ if $y=\sqrt5 \Rightarrow \lambda_1=1\sqrt5$ point satisfies the constraints

$\quad \quad$ if $y=-\sqrt5 \Rightarrow$ $y<0$, contradiction

$\quad$ case A) $\lambda_1=1\Rightarrow y=1,x=\pm2$ both points satisfy the constraints

Case 3. We are searching for feasible points at the D) constraint, inside the C) constraint

$\cdot$ C) is inactive, D) is active $\Rightarrow \lambda_1=0,x^2+y^2-5<0,y=0,\lambda_2\geq0$

$\quad\lambda_2=-2$ contradiction

Case 4. We are searching for feasible points inside C) and D) constraints

$\cdot$C) and D) are inactive $\Rightarrow \lambda_1=0,x^2+y^2-5<0,\lambda_2=0,y>0$

$\quad 2=0$ contradiction

5.Calculate the function value at the feasible solutions, pick the maximas

</table> The points 1 and 2 are the candidates for maximum. Let's call them $P_1$ and $P_2$ respectively.

In [7]:
f<-function(x,y){ x^2+2*y}
f_5<-function(x,y){ x^2+y^2}
x<- seq(-5,5, len=100)
y<- seq(-5,5, len=100)
z<- outer(x,y,f)
w<-outer(x,y,f_5)
image(x,y,z,asp=1,xlim=c(-5,5),ylim=c(-5,5))
contour(x,y,z,add=T)
contour(x,y,z,add=T,levels=6,col="blue",labels="x^2+2y=6",labcex=1)
arrows(2,1,4,2,length = 0.25,col="blue")
arrows(-2,1,-4,2,length = 0.25,col="blue")
image(x,y,w,asp=1,xlim=c(-5,5),ylim=c(-5,5))
contour(x,y,w,add=T)
contour(x,y,w,add=T,levels=5,col="blue",labels="x^2+y^2=5",labcex=1)
arrows(2,1,4,2,length = 0.25,col="blue")
arrows(-2,1,-4,2,length = 0.25,col="blue")

The gradient of the function $f(x,y)=x^2+2y$ at $P_1$ and $P_2$ is a linear combination of the gradient of active C) constraint multiplied by a $\lambda_1$ equal to 1.
In addition, $\lambda_2=0$. The FONC and complementary slackness conditions, and therefore KKT conditions are satisfied.

6.For each feasible solution:

6.a Define a Jacobian of active, nondegenerate constraints

Degenerate constraints are the active constraints with $\lambda=0$ Don't include those in the Jacobian. This topic is beyond the scope of your class.

$$\mathbf{J}=\frac{d \mathbf{f}}{d \mathbf{x}}=\left[ \frac{\partial \mathbf{f}}{\partial x_1}\cdots \frac{\partial \mathbf{f}}{\partial x_n} \right]=\left[ \frac{\partial \mathbf{g_1}}{\partial x} \frac{\partial \mathbf{g_1}}{\partial y} \right]=\left[ 2x \; 2y \right]$$

Jacobian vectors may differ between points, but for our feasible points the active constraints are the same (only constraint C is active). Jacobian of one active constraint is a gradient of that constraint.

Therefore:
Jacobian of $P_1=[4\;2]$
Jacobian of point $P_2=[-4\;2]$

6.b Find the nullspace Z of the Jacobian

$J*Z=0$

$\cdot$ For $P_1$

$[4\;2]\begin{bmatrix}z_{1} \\z_{2}\end{bmatrix}=0\Rightarrow4z_1+2z_2=0\Rightarrow z_2=-2z_1\Rightarrow Z= \begin{bmatrix}z_{1} \\-2z_{1}\end{bmatrix}$

$\cdot$ For $P_2$

$[-4\;2]\begin{bmatrix}z_{1} \\z_{2}\end{bmatrix}=0\Rightarrow -4z_1+2z_2=0\Rightarrow z_2=2z_1\Rightarrow Z= \begin{bmatrix}z_{1} \\2z_{1}\end{bmatrix}$

The resulting nullspace is a combination of all vectors orthogonal to the Jacobian of active constraints.

6.c Calculate the Hessian of the Lagrangian, all constraints considered

$H_L=\begin{bmatrix}2-2\lambda_1\;\;0 \\0\;\;\;\;-2\lambda_1\end{bmatrix}$

Lambdas for $P_1$ and $P_2$ are indifferent, therefore

$H_L(P_1)=H_L(P_2)=\begin{bmatrix}0\;\;\;\;0 \\0\;-2\end{bmatrix}$

6.d Check for positive or negative concavity of the Hessian of the Lagrangian at the nullspace of Jacobian of active constraints

$Z^T*H_L*Z$

$\cdot$ For $P_1$

$\quad [z_1\;-2z_2]\begin{bmatrix}0\;\;\;\;0 \\0\;-2\end{bmatrix}\begin{bmatrix}z_{1} \\-2z_{1}\end{bmatrix}=-8z_1^2$

$\quad$Hessian is negative definite. $P_1$ is a maximum.

$\cdot$ For $P_2$

$\quad [z_1\;2z_2]\begin{bmatrix}0\;\;\;\;0 \\0\;-2\end{bmatrix}\begin{bmatrix}z_{1} \\2z_{1}\end{bmatrix}=-8z_1^2$

$\quad$Hessian is negative definite. $P_2$ is a maximum.

PART 5. Optimization with mixed constraints

Example 5.1 Optimize $f(x,y)=(x-1)^2+y-2$ subject to $\begin{equation} \begin{cases} g_1(x,y)=y-x-1=0\\g_2(x,y)=x+y\leq2\\\end{cases}\end{equation}$

2.Define the Lagrangian

$L=x^2-2x+y-1-\lambda_1(y-x-1)-\lambda_2(x+y-2)$

3.Define the First Order Necessary Conditions

A)$\frac{\delta_L}{\delta_x}= 2x-2+\lambda_1-\lambda_2=0$

B)$\frac{\delta L}{\delta y}=1-\lambda_1-\lambda_2=0$

C)$y-x-1=0$ we treat this condition similar to an always binding inequality condition, but there is no restriction on the $\lambda_1$ value.

D)$\lambda_2\geq0,\;\;(\lambda_2=0$ if $x+y-2<0)$

Case 1. We are searching for feasible points at the D constraint. D is binding.

$x+y-2\leq0$ is binding $\Rightarrow x+y-2=0 \land \lambda_2\geq0$ $\quad$ from C) $y=x+1 \Rightarrow 2x+1-2=0 \Rightarrow x=\frac{1}{2},y=\frac{3}{2}$
from B) $\lambda_1=1-\lambda_2 \Rightarrow 1-2+1-\lambda_2-\lambda_2=0 \Rightarrow \lambda_2=0 \Rightarrow \lambda_1=1$ Point is a feasible solution.

Case 2. We are searching for feasible points inside the D constraint. D is not binding.

$x+y-2\leq0$ is not binding $\Rightarrow x+y-2<0 \land \lambda_2=0 \Rightarrow \lambda_1=1 \Rightarrow 2x=1 \Rightarrow x=\frac{1}{2} \Rightarrow y=\frac{3}{2}$, but then $x+y-2=0$. Contradiction

4. Define a Jacobian of active, nondegenerate constraints. Calculate its nullspace.

In the case of our one feasible solution, the C) constraint is binding. The D) constraint is binding, but the $\lambda_2=0$. The D) constraint is therefore not included in the Jacobian. Jacobian is therefore based on the gradient of C)

$\mathbf{J}=$$ [-1\;1]\begin{bmatrix}z_{1} \\z_{2}\end{bmatrix}=0\Rightarrow-z_1+z_2=0\Rightarrow z_1=z_2\Rightarrow Z= \begin{bmatrix}z_{1} \\z_{1}\end{bmatrix}$

5. Calculate the Hessian of the Lagrangian, all constraints considered

$H_L=\begin{bmatrix}2\;\;\;0 \\0\;\;\;\;0\end{bmatrix}$

6. Check for positive or negative concavity of the Hessian of the Lagrangian at the nullspace of Jacobian of active constraints

$\quad [z_1\;z_1]\begin{bmatrix}2\;\;\;\;0 \\0\;\;\;0\end{bmatrix}\begin{bmatrix}z_{1} \\z_{1}\end{bmatrix}=2z_1^2$ Hessian is positive definite. The point is a minimum.

In [ ]:

No. xy $\lambda_1$ $\lambda_2$ f(x,y)
1 2 1 106
2 -2 1 106
3 0 $\sqrt5$ $\frac{1}{\sqrt5}$0$2\sqrt5$